package lc2;

import org.junit.Test;

public class Ex424 {
    class Solution {
        public int characterReplacement(String s, int k) {
            char[] cs = s.toCharArray();
            int n = cs.length;
            int max = 1;
            int[] dict = new int[26];
            for (int i = 0; i < n; i++) {
                dict[cs[i] - 'A']++;
            }
            int cnt = k;
            for (char c = 'A'; c <= 'Z'; c++) {
                if (dict[c - 'A'] == 0) {
                    continue;
                }
                int lo = 0, hi = 0;
                while (hi < n) {
                    while (hi < n) {
                        if (cs[hi] != c) {
                            if (k == 0) {
                                //消耗掉k的下个位置
                                break;
                            }
                            k--;
                        }
                        hi++;
                    }
                    max = Math.max(max, hi - lo);
    
                    if (hi == n) {
                        break;
                    }
    
                    while (k == 0) {
                        if (cs[lo] != c) {
                            k++;
                        }
                        lo++;
                    }
                }
                k = cnt;
            }
            return max;
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        System.out.println(s.characterReplacement("ABBB",2));        
    }
}
